/*
https://leetcode.cn/problems/minimum-cost-for-cutting-cake-i/
3218. 切蛋糕的最小总开销 I
*/

class Solution {
public:
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        priority_queue<pair<int, int>> pq;
        for(int i = 0;i < m - 1;i++)
        {
            pq.push({horizontalCut[i], 0});
        }
        for(int i = 0;i < n - 1;i++)
        {
            pq.push({verticalCut[i], 1});
        }
        int cuth = 1, cutv = 1;
        int res = 0;
        while(!pq.empty())
        {
            bool ish = true;
            int cost = INT_MIN;
            if(!pq.empty())
            {
                cost = pq.top().first;
                if(pq.top().second == 1)
                    ish = false;
                pq.pop();
            }
            if(ish)
            {
                res += cutv * cost;
                cuth++;
            }
            else
            {
                res += cuth * cost;
                cutv++;
            }
        }
        return res;
    }
};
